<?php

namespace lib\Rpn;

class MathRpn
{
    /**
     * input
     *
     * @var string
     */
    private $_input = '';

    /** input array
     *
     * @var array
     */
    private $_input_array = array();

    /**
     * Array with output expression in RPN
     *
     * @var array
     */
    private $_output = array();

    /**
     * Temporary stack
     *
     * @var array
     */
    private $_stack = array();

    /**
     *  Value of expression
     *
     * @var float
     */
    private $_value = 0.0;

    /**
     *  error
     *
     * @var null
     */
    private $_error = null;

    /**
     * Timer
     *
     * @var float
     */
    private $_timer = 0.0;

    /**
     *
     * operator => (名称, 优先级, 参数个数, 函数)
     *
     * @var array
     */
    private $_operation = array(
        '(' => array('left bracket', 12),
        ')' => array('right bracket', 12),
        '!' => array('non', 11, 1, '_non'),
        '+' => array('sum', 9, 2, '_sum'),
        '-' => array('difference', 9, 2, '_difference'),
        '*' => array('multiplication', 10, 2, '_multiplication'),
        '/' => array('division', 10, 2, '_division'),
        '>' => array('greaterThan', 8, 2, '_greaterThan'),
        '>=' => array('greaterThanEqual', 8, 2, '_greaterThanEqual'),
        '<' => array('lessThan', 8, 2, '_lessThan'),
        '<=' => array('lessThanEqual', 8, 2, '_lessThanEqual'),
        '==' => array('doubleEqual', 7, 2, '_doubleEqual'),
        '!=' => array('notEqual', 7, 2, '_notEqual'),
        '&&' => array('doubleAnd', 4, 2, '_doubleAnd'),
        '&' => array('and', 6, 2, '_and'),
        '||' => array('doubleOr', 3, 2, '_doubleOr'),
        '|' => array('or', 5, 2, '_or')
    );

    /**
     * 返回错误
     *
     * @param $error
     * @return mixed
     */
    private function _raiseError($error)
    {
        return ($error);
    }

    /**
     * 计算表达式 the $input expression
     *
     * @param string $input
     * @return float|object
     */
    public function calculate($input)
    {

        if ($input == '') {
            $this->_error = $this->_raiseError('空input');

            return $this->_error;
        }

        $this->_input = $input;
        $this->_stringToArray();

        if ($this->_error <> null) {
            return $this->_error;
        }

        $this->_arrayToRpn();
        if ($this->_error <> null) {
            return $this->_error;
        }

        $this->_rpnToValue();
        if ($this->_error <> null) {
            return $this->_error;
        }

        return $this->_value;
    }

    /**
     * Return a input array
     *
     * @return array Input array
     * @access public
     */
    public function getInputArray()
    {
        return $this->_input_array;
    }

    /**
     * Return a RPN array
     *
     * @return array RPN array
     * @access public
     */
    public function getRpnArray()
    {
        return $this->_output;
    }

    /**
     * Return a counting time in second
     *
     * @return float Counting time in seconds
     * @access public
     */
    public function getTimer()
    {
        return $this->_timer;
    }

    /**
     * Check that $key is a key of $array (conformity to php<4.1.0)
     *
     * @param string  $key
     * @param array   $array
     * @param integer $type 0 - return true if $key is $array's key, 1 - return true if $key is $array's key and there
     *                      isn't any occurrence of $key in another $array's key
     * @return boolean true when $key is a key of $array, or false
     * @access private
     */

    private function _keyExists($key, $array, $type)
    {
        $keys = array_keys($array);

        if ($type == 1) {
            $count = 0;
            while (list($keys_key, $keys_val) = each($keys)) {
                if (is_integer(strpos($keys_val, $key)) && (strpos($keys_val, $key) == 0)) {
                    $count++;
                }
            }
            if (($count == 1) && in_array($key, $keys)) {
                return true;
            } else {
                return false;
            }
        } else {
            if (in_array($key, $keys)) {
                return true;
            } else {
                return false;
            }
        }
    }

    /**
     * Check that $value is nan (conformity to php<4.2.0)
     *
     * @param float $value checking value
     * @return boolean true when $value is nan, or false
     * @access private
     */
    private function _isNan($value)
    {
        if (function_exists('is_nan')) {
            return is_nan($value);
        } else {
            if ((substr($value, -3) == 'IND') || (substr($value, -3) == 'NAN')) {
                return true;
            } else {
                return false;
            }
        }
    }

    /**
     * Check that $value is infinite (conformity to php<4.2.0)
     *
     * @param float $value checking value
     * @return boolean true when $value is infinite, or false
     * @access private
     */
    private function _isInfinite($value)
    {
        if (function_exists('is_finite')) {
            return !is_finite($value);
        } else {
            if (substr($value, -3) == 'INF') {
                return true;
            } else {
                return false;
            }
        }
    }

    /**
     * Change input expression into array
     *
     * @return array Input expression changed into array
     * @access private
     */
    private function _stringToArray()
    {
        $temp_operator = null;
        $temp_value = null;

        $this->_input = str_replace(" ", "", $this->_input);

        for ($i = 0; $i < strlen($this->_input); $i++) {
            if ($this->_input[$i] == ' ') {
                if ($temp_operator != null) {
                    array_push($this->_input_array, $temp_operator);
                    $temp_operator = null;
                }
                if ($temp_value != null) {
                    array_push($this->_input_array, $temp_value);
                    $temp_value = null;
                }
            } elseif (($temp_value == null) && $temp_operator != ')' && (!array_key_exists($temp_operator,
                        $this->_operation) || !array_key_exists(2,
                        $this->_operation[$temp_operator]) || $this->_operation[$temp_operator][2] > 0) && ($this->_input[$i] == '-')) {
                if ($temp_operator != null) {
                    array_push($this->_input_array, $temp_operator);
                    $temp_operator = null;
                }

                array_push($this->_input_array, '-1');
                array_push($this->_input_array, '*');
            } elseif ((is_numeric($this->_input[$i])) || ($this->_input[$i] == '.')) {
                if ($temp_operator != null) {
                    array_push($this->_input_array, $temp_operator);
                    $temp_operator = null;
                }

                $temp_value .= $this->_input[$i];
            } else {
                if ($this->_keyExists($temp_operator, $this->_operation, 1)) {
                    array_push($this->_input_array, $temp_operator);
                    $temp_operator = null;
                }

                if ($temp_value != null) {
                    array_push($this->_input_array, $temp_value);
                    $temp_value = null;
                }

                $temp_operator .= $this->_input[$i];
            }
        }

        if ($temp_operator != null && $temp_operator != ' ') {
            array_push($this->_input_array, $temp_operator);
        } elseif ($temp_value != null && $temp_value != ' ') {
            array_push($this->_input_array, $temp_value);
        }

        $this->_testInput();

        return $this->_input_array;
    }

    /**
     * Check input array and return correct array or a PEAR Error
     *
     * @return object Null or a PEAR Error
     * @access private
     */
    private function _testInput()
    {
        if (!count($this->_input_array)) {
            $this->_input_array = null;
            $this->_error = $this->_raiseError('Undefined input array');

            return $this->_error;
        }

        $bracket = 0;
        for ($i = 0; $i < count($this->_input_array); $i++) {
            if ($this->_input_array[$i] == '(') {
                $bracket++;
            }
        }
        for ($i = 0; $i < count($this->_input_array); $i++) {
            if ($this->_input_array[$i] == ')') {
                $bracket--;
            }
        }

        if ($bracket <> 0) {
            $this->_input_array = null;
            $this->_error = $this->_raiseError('Syntax error');

            return $this->_error;
        }

        for ($i = 0; $i < count($this->_input_array); $i++) {
            if ((!is_numeric($this->_input_array[$i])) && (!$this->_keyExists($this->_input_array[$i],
                    $this->_operation, 0))) {
                $error_operator = $this->_input_array[$i];
                $this->_input_array = null;
                $this->_error = $this->_raiseError('Undefined operator \'' . $error_operator . '\'');

                return $this->_error;
            }
        }

        $this->_error = null;

        return $this->_error;
    }

    /**
     * Add value to the end of stack
     *
     * @param string $value Value to add into stack
     * @access private
     */
    private function _stackAdd($value)
    {
        array_push($this->_stack, $value);
    }

    /**
     * Delete and return value from the end of stack
     *
     * @return string Value deleted from stack
     * @access private
     */
    private function _stackDelete()
    {
        return array_pop($this->_stack);
    }

    /**
     * Return priority of value
     *
     * @param $value
     * @return mixed
     */
    private function _priority($value)
    {
        return $this->_operation[$value][1];
    }

    /**
     * Return priority of value from the end of stack
     *
     * @return mixed
     */
    private function _stackPriority()
    {
        $value = $this->_stackDelete();
        $this->_stackAdd($value);

        return $this->_priority($value);
    }

    /**
     * Return true whene the stack is empty
     *
     * @return bool
     */
    private function _stackEmpty()
    {
        if (count($this->_stack)) {
            return false;
        } else {
            return true;
        }
    }

    /**
     * Add value into output array
     *
     * @param $value
     */
    private function _outputAdd($value)
    {
        if ($value <> '(') {
            array_push($this->_output, $value);
        }
    }

    /**
     * Change input array into RPN array
     *
     * @return array
     */
    private function _arrayToRpn()
    {

        if ($this->_error <> null) {
            $this->_output = array();

            return $this->_output;
        }

        for ($i = 0; $i < count($this->_input_array); $i++) {

            $temp = $this->_input_array[$i];

            if (is_numeric($temp)) {
                $this->_outputAdd($temp);
            } else {
                if ($temp == ')') {
                    while (!$this->_stackEmpty() && ($this->_stackPriority() >= 1)) {
                        $this->_outputAdd($this->_stackDelete());
                    }
                    if (!$this->_stackEmpty()) {
                        $this->_stackDelete();
                    }

                } elseif ($temp == '(') {
                    $this->_stackAdd($temp);
                } elseif (($this->_stackEmpty()) || (($this->_priority($temp) > $this->_stackPriority()))) {
                    $this->_stackAdd($temp);
                } else {
                    while (!$this->_stackEmpty() && ($this->_priority($temp) <= $this->_stackPriority())) {
                        $this->_outputAdd($this->_stackDelete());
                    }
                    $this->_stackAdd($temp);
                }

            }

        }

        while (!$this->_stackEmpty()) {
            $this->_outputAdd($this->_stackDelete());
        }

        return $this->_output;
    }

    /**
     * Return position of the first operator in array
     *
     * @param $array
     * @return int
     */
    private function _nextOperator($array)
    {
        $pos = 0;
        while (is_numeric($array[$pos]) || $array[$pos] === false || $array[$pos] === true) {
            $pos++;
            if ($pos >= count($array)) {
                return -1;
            }
        }

        return $pos;

    }

    /**
     * Delete from array operator [posision $pos] and its argument and insert new value
     *
     * @param $temp
     * @param $pos
     * @param $arg
     * @param $result
     * @return array
     */
    private function _refresh($temp, $pos, $arg, $result)
    {
        $temp1 = array_slice($temp, 0, $pos - $arg);
        $temp1[] = $result;
        $temp2 = array_slice($temp, $pos + 1);

        return array_merge($temp1, $temp2);
    }

    /**
     * +
     *
     * @param $temp
     * @param $pos
     * @return mixed
     */
    private function _sum($temp, $pos)
    {
        return $temp[$pos - 2] + $temp[$pos - 1];
    }

    /**
     * >
     *
     * @param $temp
     * @param $pos
     * @return mixed
     */
    private function _greaterThan($temp, $pos)
    {
        return $temp[$pos - 2] > $temp[$pos - 1];
    }

    /**
     * >=
     *
     * @param $temp
     * @param $pos
     * @return mixed
     */
    private function _greaterThanEqual($temp, $pos)
    {
        return $temp[$pos - 2] >= $temp[$pos - 1];
    }

    /**
     * <=
     *
     * @param $temp
     * @param $pos
     * @return mixed
     */
    private function _lessThanEqual($temp, $pos)
    {
        return $temp[$pos - 2] <= $temp[$pos - 1];
    }

    /**
     * <
     *
     * @param $temp
     * @param $pos
     * @return mixed
     */
    private function _lessThan($temp, $pos)
    {
        return $temp[$pos - 2] < $temp[$pos - 1];
    }

    /** &&
     * @param $temp
     * @param $pos
     * @return mixed
     */
    private function _doubleAnd($temp, $pos)
    {
        return $temp[$pos - 2] && $temp[$pos - 1];
    }

    /** ==
     * @param $temp
     * @param $pos
     * @return mixed
     */
    private function _doubleEqual($temp, $pos)
    {
        return $temp[$pos - 2] == $temp[$pos - 1];
    }

    /** !=
     * @param $temp
     * @param $pos
     * @return mixed
     */
    private function _notEqual($temp, $pos)
    {
        return $temp[$pos - 2] != $temp[$pos - 1];
    }

    /**
     * &
     * @param $temp
     * @param $pos
     * @return int
     */
    private function _and($temp, $pos)
    {
        return $temp[$pos - 2] & $temp[$pos - 1];
    }

    /**
     * ||
     * @param $temp
     * @param $pos
     * @return int
     */
    private function _doubleOr($temp, $pos)
    {
        return $temp[$pos - 2] || $temp[$pos - 1];
    }

    /**
     * |
     * @param $temp
     * @param $pos
     * @return int
     */
    private function _or($temp, $pos)
    {
        return $temp[$pos - 2] | $temp[$pos - 1];
    }

    /**
     * @param $temp
     * @param $pos
     * @return mixed
     */
    private function _difference($temp, $pos)
    {
        return $temp[$pos - 2] - $temp[$pos - 1];
    }

    /**
     * @param $temp
     * @param $pos
     * @return mixed
     */
    private function _multiplication($temp, $pos)
    {
        return $temp[$pos - 2] * $temp[$pos - 1];
    }

    /**
     * @param $temp
     * @param $pos
     * @return float|int|null
     */
    private function _division($temp, $pos)
    {
        if ($temp[$pos - 1] == 0) {
            $this->_error = $this->_raiseError('Division by 0');
            $this->_value = null;

            return $this->_value;
        }

        return $temp[$pos - 2] / $temp[$pos - 1];
    }

    /** !
     * @param $temp
     * @param $pos
     * @return bool
     */
    private function _non($temp, $pos)
    {
        return !$temp[$pos - 1];
    }

    /**
     * Calculate RPN Expression and return value
     *
     * @return float|mixed|null
     */
    function _rpnToValue()
    {

        $time1 = $this->_getMicroTime();

        if ($this->_error <> null) {
            $this->_value = null;

            return $this->_value;
        }

        $this->_value = 0;
        $temp = $this->_output;

        do {

            $pos = $this->_nextOperator($temp);

            if ($pos == -1) {
                var_dump($temp);
                $this->_error = $this->_raiseError('Syntax error 3');
                $this->_value = null;

                return $this->_value;
            }

            $operator = $this->_operation[$temp[$pos]];

            $arg = $operator[2];

            $function = $operator[3];

            if (($arg == 2) && (!isset($temp[$pos - 1]) || !isset($temp[$pos - 2]))) {
                $this->_error = $this->_raiseError('Syntax error 1 ');
                $this->_value = null;

                return $this->_value;
            } elseif (($arg == 1) && (!isset($temp[$pos - 1]))) {
                $this->_error = $this->_raiseError('Syntax error 2');
                $this->_value = null;

                return $this->_value;
            }

            if (is_array($function)) {

                if ($arg == 2) {
                    $arg_array = array($temp[$pos - 2], $temp[$pos - 1]);
                } elseif ($arg == 1) {
                    $arg_array = array($temp[$pos - 1]);
                } else {
                    $arg_array = array();
                }

                if ($function['type'] == 'userFunction') {
                    $this->_value = call_user_func_array($function['function'], $arg_array);
                } else {
                    $function_array = array(&$function['class'], $function['method']);
                    $this->_value = call_user_func_array($function_array, $arg_array);
                }
            } else {
                $this->_value = $this->$function($temp, $pos);
            }

            if ($this->_isNan($this->_value)) {
                $this->_error = $this->_raiseError('NAN value');
                $this->_value = null;

                return $this->_value;
            } elseif ($this->_isInfinite($this->_value)) {
                $this->_error = $this->_raiseError('Infinite value');
                $this->_value = null;

                return $this->_value;
            } elseif (is_null($this->_value)) {
                return $this->_value;
            }

            $temp = $this->_refresh($temp, $pos, $arg, $this->_value);
        } while (count($temp) > 1);

        $this->_value = $temp[0];

        $time2 = $this->_getMicroTime();

        $this->_timer = $time2 - $time1;

        return $this->_value;
    }

    /**
     * Return a time in second
     *
     * @return float
     */
    private function _getMicroTime()
    {
        list($usec, $sec) = explode(" ", microtime());

        return ((float)$usec + (float)$sec);
    }

}

/*
$array = [
    1 => ['(', ')'],
    2 => ['!'],
    3 => ['*', '/'],
    4 => ['+', '-'],
    6 => ['>', '>=', '<', '<='],
    7 => ['==', '!='],
    8 => ['&'],
    10 => ['|'],
    11 => ['&&'],
    12 => ['||']
];

$i = 12;
foreach ($array as $key => $val) {
    echo $i--;
    var_dump($val);
    echo "\n";
}

$infix_expression = "(3+2)>=2 && 1==1";
$rpn = new Math_Rpn();

var_dump($rpn->calculate($infix_expression));
*/
?>